package reverseBookList;

import java.util.*;

public class Solution {
    public class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }
    public int[] reverseBookList(ListNode head) {
        List<Integer> list = new ArrayList<>();
        dfs(head,list);
        int[] ans = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            ans[i] = list.get(i);
        }
        return ans;
    }
    private void dfs(ListNode head,List<Integer> list){
        if(head == null) {
            return;
        }
        dfs(head.next,list);
        list.add(head.val);
    }
    public int[] trainingPlan(int[] actions) {
        int i = 0,j = actions.length-1;
        while (i<j) {
            if(actions[i]%2!=0) {
                i++;
            } else if (actions[j]%2==0) {
                j--;
            } else {
                int t = actions[i];
                actions[i++] = actions[j];
                actions[j--] = t;
            }
        }
        return actions;
    }
    public ListNode trainingPlan(ListNode head, int cnt) {
        ListNode slow = head;
        ListNode fast = head;
        while (cnt-->0) {
            fast = fast.next;
        }
        while (fast!=null) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }
    public int[] twoSum(int[] price, int target) {
        Arrays.sort(price);
        int i = 0,j = price.length-1;
        while (i<j) {
            if(price[i]+price[j] < target) {
                i++;
            } else if (price[i]+price[j] > target){
                j--;
            } else {
                return new int[]{price[i],price[j]};
            }
        }
        return null;
    }
    public int[][] fileCombination(int target) {
        List<int[]> list = new ArrayList<>();
        int l = 1,r = 2;
        while (l<r && r<target) {
            int sum = (l+r)*(r-l+1)/2;
            if(sum>target) {
                l++;
            } else if (sum<target) {
                r++;
            } else {
                int[] ans = new int[r-l+1];
                for (int i = l; i <= r; i++) {
                    ans[i-l] = i;
                }
                list.add(ans);
                l++;
                r++;
            }
        }
        return list.toArray(new int[list.size()][]);
    }
    public String dynamicPassword(String password, int target) {
        StringBuilder sb = new StringBuilder();
        for (int i = target; i < target+password.length(); i++) {
            sb.append(password.charAt(i%password.length()));
        }
        return sb.toString();
    }
    public String compressString(String s) {
        StringBuilder sb = new StringBuilder();
        char c = s.charAt(0);
        int i = 0;
        int count = 0;
        while (i<s.length()) {
            if(s.charAt(i) == c && i!=s.length()-1) {
                count++;
            } else {
                sb.append(c).append(count);
                count = 1;
                c = s.charAt(i);
            }
            i++;
        }
        sb.append(c).append(count);
        return sb.length() < s.length()?sb.toString():s;
    }
    public ListNode removeDuplicateNodes(ListNode head) {
        // 移除重复节点
        if(head == null) return head;
        Set<Integer> set = new HashSet<>();
        ListNode cur = head;
        set.add(cur.val);
        while (cur.next!=null) {
            if(!set.add(cur.next.val)) {
                cur.next = cur.next.next;
            } else {
                cur = cur.next;
            }
        }
        return head;
    }

}
